Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds).
Your system should accept a timestamp parameter (in seconds granularity), and you may assume that calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing). Several hits may arrive roughly at the same time.
Implement the HitCounter class:
HitCounter()Initializes the object of the hit counter system.void hit(int timestamp)Records a hit that happened attimestamp(in seconds). Several hits may happen at the sametimestamp.int getHits(int timestamp)Returns the number of hits in the past 5 minutes fromtimestamp(i.e., the past300seconds).
Example 1:
Input ["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"] [[], [1], [2], [3], [4], [300], [300], [301]] Output [null, null, null, null, 3, null, 4, 3] Explanation HitCounter hitCounter = new HitCounter(); hitCounter.hit(1); // hit at timestamp 1. hitCounter.hit(2); // hit at timestamp 2. hitCounter.hit(3); // hit at timestamp 3. hitCounter.getHits(4); // get hits at timestamp 4, return 3. hitCounter.hit(300); // hit at timestamp 300. hitCounter.getHits(300); // get hits at timestamp 300, return 4. hitCounter.getHits(301); // get hits at timestamp 301, return 3.
Constraints:
1 <= timestamp <= 2 * 109- All the calls are being made to the system in chronological order (i.e.,
timestampis monotonically increasing). - At most
300calls will be made tohitandgetHits.
Follow up: What if the number of hits per second could be huge? Does your design scale?
Average Rating: 4.25 (16 votes)
Approach #1: Using Queue
Intuition
A key observation here is that all the timestamps that we will encounter are going to be in increasing order. Also as the timestamps' value increases we have to ignore the timestamps that occurred previously (having a difference of 300 or more with the latest timestamp). This is the case of considering the elements in the FIFO manner (First in first out) which is best solved by using the "queue" data structure.
Algorithm
We will add each timestamp to the queue in the hit method and will remove all the timestamps with difference greater than or equal to 300 from the queue inside getHits. The answer returned from the getHits method is then simply the size of the queue.
Below is the implementation of this approach.
Complexity Analysis
-
Time Complexity
-
hit- Since inserting a value in the queue takes place in O(1) time, hencehitmethod works in O(1). -
getHits- Assuming a total of n values present in the queue at a time and the total number of timestamps encountered throughout is N. In the worst case scenario, we might end up removing all the entries from the queue ingetHitsmethod if the difference in timestamp is greater than or equal to 300. Hence in the worst case, a "single" call to thegetHitsmethod can take O(n) time. However, we must notice that each timestamp is processed only twice (first while adding the timestamp in the queue inhitmethod and second while removing the timestamp from the queue in thegetHitsmethod). Hence if the total number of timestamps encountered throughout is N, the overall time taken bygetHitsmethod is O(N). This results in an amortized time complexity of O(1) for a single call togetHitsmethod.
-
-
Space Complexity: Considering the total timestamps encountered throughout to be N, the queue can have upto N elements, hence overall space complexity of this approach is O(N).
Approach #2: Using Deque with Pairs
Consider the follow up, where we have multiple hits arriving at the "same" timestamps. We can optimize Approach 1 even further. In this approach, we'll not only keep the timestamps but will also keep the count of the timestamps as well. For example, if we call hit method 5 times for timestamp = 1, the queue in case of Approach 1 will look like [1, 1, 1, 1, 1]. This will lead to 5 removals in the getHits method when we remove the value 1 from the queue. To avoid this repetitive removals of the same value, in Approach 2, we'll store the value as (1, 5) where the first value 1 is the timestamp and the second value 5 is the count. For this, we'll use the "deque" data structure which allows us to insert and delete values from both the ends of the queue.
Algorithm
The updated algorithm in Approach 2 is as follows.
-
If we encounter the hit for the same timestamp, instead of appending a new entry in the deque, we simply increment the count of the latest timestamp.
-
In order to keep the track of total number of elements (for the last 300 seconds), we also use a variable
totalwhich we initialize to0and keep updating as we add or remove the elements from the queue. We increment the value oftotalby 1 whenhitmethod is called and we decrement by the value oftotalby the count of the timestamp that we remove from the queue.
Below is the implementation of this approach.
Complexity Analysis
In the worst case, when there are not many repetitions, the time complexity and space complexity of Approach 2 is the same as Approach 1. However in case we have repetitions (say k repetitions of a particular ith timestamp), the time complexity and space complexities are as follows.
-
Time Complexity:
-
hit- O(1). -
getHits- If there are a total of n pairs present in the deque, worst case time complexity can be O(n). However, by clubbing all the timestamps with same value together, for the ith timestamp with k repetitions, the time complexity is O(1) as here, instead of removing all those k repetitions, we only remove a single entry from the deque.
-
-
Space complexity: If there are a total of N elements that we encountered throughout, the space complexity is O(N) (similar to Approach 1). However, in the case of repetitions, the space required for storing those k values O(1).
I did this without queues. Only maps.
def __init__(self):
"""
Initialize your data structure here.
"""
self.hits = {}
def hit(self, timestamp: int) -> None:
"""
Record a hit.
@param timestamp - The current timestamp (in seconds granularity).
"""
if timestamp not in self.hits:
self.hits[timestamp] = 0
self.hits[timestamp] += 1
def getHits(self, timestamp: int) -> int:
"""
Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity).
"""
begin = timestamp - 300
hits_for_ts = 0
for i in range(begin+1, timestamp+1):
if i in self.hits:
hits_for_ts += self.hits[i]
return hits_for_ts
getHits is still constant time, as it is always looping 300 times (this is negligible when you have millions of timestamp). The proposed solution does similar stuff but seems overly complex
Deque solution approach #2 is not really optimized for space. You can reduce space complexity to O(1), since at any given time you need to keep at max 300 pairs. Solution is to also do pop while registering the hit and therefore maintaining a constant space complexity. Remember always popping is capped to 300 in both hit() and getHits() API.
February 16, 2021 5:59 PM
How come the official solution is not the most optimized one?
I posted a solution where hit function time complexity is O(1) and getHits func time complexity is O(log n) - https://leetcode.com/problems/design-hit-counter/discuss/1068290/C%2B%2B-w-full-explanation.-Beats-100-runtime.-hit-func-O(1)-and-getHits-func-O(logn)
Short c++ solution (20 lines).
Time complexity: hit O(1) ; getHits O(logN).
Space used O(n).
What do you think about it?
class HitCounter {
public:
void hit(int timestamp) {
hits.push_back(timestamp);
// Prevent overloading.
if (hits.front() < timestamp - 300)
hits.pop_front();
}
int getHits(int timestamp) {
auto it = upper_bound(hits.begin(), hits.end(), timestamp - 300);
return hits.end() - it;
}
private:
deque<int> hits;
};March 16, 2021 9:19 AM
A scalable and fast circular buffer solution:
https://leetcode.com/problems/design-hit-counter/discuss/1111730/Scalable-Circular-Buffer-Solution
Simple solution using map in Go which also accounts for concurrent hits.
type HitCounter struct {
mu sync.Mutex
hits map[int]int
}
/** Initialize your data structure here. */
func Constructor() HitCounter {
return HitCounter{
hits: make(map[int]int),
}
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
func (this *HitCounter) Hit(timestamp int) {
this.mu.Lock()
this.hits[timestamp] = this.hits[timestamp] + 1
this.mu.Unlock()
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
func (this *HitCounter) GetHits(timestamp int) int {
this.mu.Lock()
defer this.mu.Unlock()
var start = timestamp - 299
if start < 0 {
start = 1
}
var noOfHits int
for i := start; i <= timestamp; i++ {
noOfHits = noOfHits + this.hits[i]
}
return noOfHits
}
I believe there is an error in the C++ solution 2 -- It explains using a deque, but it does not, and in the hit() method it checks the .front() rather than the .back()
Java solution using Map
import java.util.Optional;
class HitCounter {
private Map<Integer, Integer> hitMap;
/** Initialize your data structure here. */
public HitCounter() {
hitMap = new HashMap<>();
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
if(hitMap.containsKey(timestamp)) {
hitMap.put(timestamp, hitMap.get(timestamp)+1);
} else {
hitMap.put(timestamp, 1);
}
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
Optional<Integer> hits;
if(timestamp <= 300) {
// Find all the entries in the map from the range 1 to 300
hits = hitMap.entrySet().stream()
.filter(e -> e.getKey() <= 300)
.map(Map.Entry::getValue)
.reduce(Integer::sum);
} else {
// Find all the entries in the map from the range timestamp to timestamp-300
// timestamp-300
hits = hitMap.entrySet().stream()
.filter(e -> e.getKey() > timestamp - 300)
.map(Map.Entry::getValue)
.reduce(Integer::sum);
}
if(hits.isPresent())
return hits.get();
else
return 0;
}
}
You don't have any submissions yet.
xxxxxxxxxxclass HitCounter {public: /** Initialize your data structure here. */ HitCounter() { } /** Record a hit. @param timestamp - The current timestamp (in seconds granularity). */ void hit(int timestamp) { } /** Return the number of hits in the past 5 minutes. @param timestamp - The current timestamp (in seconds granularity). */ int getHits(int timestamp) { }};/** * Your HitCounter object will be instantiated and called as such: * HitCounter* obj = new HitCounter(); * obj->hit(timestamp); * int param_2 = obj->getHits(timestamp); */